/*
题目描述：长度为n的绳子，剪成m段，使得每段乘积最大
方法：
可以转化为小问题，自底向上求解（将原本递归地重复计算结果保存起来）
1. 动态规划
2. 贪心
 */
public class E14 {
    public static void main(String[] args){
        int len = 18;
        int res = maxProductAfterCutting2(len);
        System.out.println(res);
    }

    public static int maxProductAfterCutting(int len){
        if(len < 2){
            return 0;
        }
        if(len == 2){
            return 1;
        }
        if(len == 3){
            return 2;
        }
        int[] f = new int[len + 1];
        f[0] = 0;
        f[1] = 1;
        f[2] = 2;
        f[3] = 3;

        int max = 0;
        for(int i = 4; i <= len; i++){
            max = 0;
            //在长度为i的绳子上尝试所有切割方案，并将最大乘积结果存入f[i]
            for(int j = 1; j <= i/2; j++){
                f[i] = Math.max(max, f[j] * f[i - j]);
            }
        }
        max = f[len];
        return max;
    }

    public static int maxProductAfterCutting2(int len){
        if(len < 2){
            return 0;
        }
        if(len == 2){
            return 1;
        }
        if(len == 3){
            return 2;
        }
        //尽可能多地减去长度为3的绳子段
        int timesOf3 = len / 3;
        //当绳子长度为4时，剪成2+2
        if(len - timesOf3 * 3 == 1){
            timesOf3 -= 1;
        }
        int timesOf2 = (len - timesOf3 * 3)/2;

        return (int)(Math.pow(3, timesOf3)) * (int)(Math.pow(2, timesOf2));
    }
}
